package com.bascker.algorithm.practice.arr.easy.maximum_product;

import java.util.Arrays;
import java.util.Objects;

// 预排序: 题目并没有对原数组做限制，如不允许改变原数组的排列情况等。因此我们可以对原数组进行预处理
// 时间复杂度：取决于排序算法的复杂度, 此处为 O(NlogN) => Arrays.sort() 最坏情况下时间复杂度为 O(NlogN)
// 空间复杂度：取决于排序算法的复杂度，此处为 O(logN)
public class Solution2 {

    public int maximumProduct(int[] nums) {
        if (Objects.isNull(nums) || nums.length < 3) {
            return 0;
        }

        // 预处理：升序
        Arrays.sort(nums);
        int n = nums.length;

        // 场景判断
        // 1. 数组元素全正数、负数：最大值一定是最后面 3 个元素的乘积
        int max = nums[n - 1] * nums[n - 2] * nums[n - 3];

        // 2. 数组元素正数、负数都有：最大值可能是最后3个元素，也可能是最前面 2 个元素和最后一个元素的乘积
        // 如 -1、-2、3、0，排序后是 -2、-1、0、3，其最后3个元素乘积为 -1 * 0 * 3 = 0，实际其最大值为 -2 * -1 - 3 = 6
        max = Math.max(max, nums[0] * nums[1] * nums[n - 1]);

        return max;
    }

}
